﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace GoodroommateComputingPlatform.Algorithms.Kmeans
{

    /// <summary>
    /// 用于从对象中提取指数的委托
    /// </summary>
    /// <typeparam name="T">聚类数据对象类型</typeparam>
    /// <param name="obj">当前聚类数据对象</param>
    /// <param name="vector">指数列表</param>
    public delegate void KmeansVectorAction<T>(T obj, IList<double> vector);

    /// <summary>
    /// Kmeans聚类算法核心
    /// </summary>
    /// <typeparam name="T">数据点的类型</typeparam>
    public class KmeansCore<T>
    {

        /// <summary>
        /// 聚类组数
        /// </summary>
        public int GroupCount { get; set; }

        /// <summary>
        /// 用于从对象中提取指数的委托
        /// </summary>
        public KmeansVectorAction<T> VectorAction { get; set; }

        private static class KmeansObjectWrapper
        {
            public static KmeansObjectWrapper<TKmeansObject> Create<TKmeansObject>(TKmeansObject obj, double[] vector)
            {
                return new KmeansObjectWrapper<TKmeansObject>(obj, vector);
            }
        }
        private struct KmeansObjectWrapper<TKmeansObject>
        {
            public TKmeansObject Object { get; set; }

            public double[] Vector { get; set; }

            public KmeansObjectWrapper(TKmeansObject obj, double[] vector)
            {
                Object = obj;
                Vector = vector;
            }

            public KmeansCenterVector ToVecotr()
            {
                return new KmeansCenterVector() { Vector = Vector };
            }
        }

        private struct KmeansCenterVector
        {
            public double[] Vector { get; set; }

            public KmeansCenterVector(double[] vector)
            {
                Vector = vector;
            }
        }

        /// <summary>
        /// 将给定的数据使用Kmeans算法聚类成GroupCount组。
        /// </summary>
        /// <param name="items">待聚类的数据</param>
        /// <returns>聚类后的数据，数组长度等于组数</returns>
        public List<T>[] DoKmeans(List<T> items)
        {
            if (items == null)
                throw new ArgumentNullException(nameof(items));
            if (items.Count == 0)
                throw new ArgumentException($"{ nameof(items) } can not be empty");
            if (GroupCount < 1)
                throw new ArgumentOutOfRangeException(nameof(GroupCount));

            // 计算Vector
            var witems = new List<KmeansObjectWrapper<T>>();
            var tmpList = new List<double>();
            foreach (var item in items)
            {
                tmpList.Clear();
                VectorAction.Invoke(item, tmpList);
                witems.Add(KmeansObjectWrapper.Create(item, tmpList.ToArray()));
            }

            // 初始聚类中心
            int actualGroupCount;
            var initItems = KmeansHelper.InitializeCenterVectors(witems, GroupCount, out actualGroupCount);

            // 初始化结果数组
            var result = new List<KmeansObjectWrapper<T>>[actualGroupCount];
            for (int i = 0; i < actualGroupCount; i++)
                result[i] = new List<KmeansObjectWrapper<T>>();

            double[] dists = new double[actualGroupCount];
            bool isCenterChanged = true;
            while (isCenterChanged)
            {
                isCenterChanged = false;

                // 清空结果数组
                for (int i = 0; i < actualGroupCount; i++)
                    result[i].Clear();

                // 一轮聚类
                foreach (var item in witems)
                {
                    for (int i = 0; i < actualGroupCount; i++)
                        dists[i] = KmeansHelper.CalculateDistence(item, initItems[i]);

                    var distIndex = KmeansHelper.FindMinimumDistence(dists);
                    result[distIndex].Add(item);
                }

                // 计算新的中心
                for (int i = 0; i < actualGroupCount; i++)
                {
                    var player_new = KmeansHelper.CreatePseudoCenterObject(result[i]);
                    var player_old = initItems[i];
                    if (!KmeansHelper.IsPlayerEqual(player_old, player_new))
                    {
                        isCenterChanged = true;
                        initItems[i] = new KmeansCenterVector(player_new);
                    }
                }
            }

            return result.Select(group => group.Select(i => i.Object).ToList()).ToArray();
        }

        private static class KmeansHelper
        {

            /// <summary>
            /// 初始化聚类中心
            /// </summary>
            /// <typeparam name="TKmeansObject">聚类数据对象类型</typeparam>
            /// <param name="list">聚类数据对象列表</param>
            /// <param name="groupCount">聚类组数</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns></returns>
            public static KmeansCenterVector[] InitializeCenterVectors<TKmeansObject>(IEnumerable<KmeansObjectWrapper<TKmeansObject>> list, int groupCount, out int actualGroupCount)
            {
                var result = new KmeansCenterVector[groupCount];
                int addedCount = 0;
                foreach (var item in list)
                {
                    bool contains = false;
                    for (int i = 0; i < addedCount; i++)
                        if (IsPlayerEqual(item, result[i]))
                        {
                            contains = true;
                            break;
                        }
                    if (!contains)
                        result[addedCount++] = item.ToVecotr();
                    if (addedCount == groupCount)
                        break;
                }
                actualGroupCount = addedCount;
                return result;
            }

            /// <summary>
            /// 比较是否两个对象是否属性一致
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="obj1">第一个对象</param>
            /// <param name="obj2">第二个对象</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns></returns>
            public static bool IsPlayerEqual<TKmeansObject>(KmeansObjectWrapper<TKmeansObject> obj1, KmeansObjectWrapper<TKmeansObject> obj2)
            {
                if (object.ReferenceEquals(obj1.Object, obj2.Object))
                    return true;
                if (obj1.Object == null || obj2.Object == null)
                    return false;

                if (obj1.Vector.Length != obj1.Vector.Length)
                    return false;

                for (int i = 0; i < obj1.Vector.Length; i++)
                    if (obj1.Vector[i] != obj1.Vector[i])
                        return false;

                return true;
            }

            /// <summary>
            /// 比较是否两个对象是否属性一致
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="obj1">第一个对象</param>
            /// <param name="obj2">第二个对象</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns></returns>
            public static bool IsPlayerEqual<TKmeansObject>(KmeansObjectWrapper<TKmeansObject> obj1, KmeansCenterVector obj2)
            {
                if (object.ReferenceEquals(obj1.Vector, obj2.Vector))
                    return true;
                if (obj1.Vector == null || obj2.Vector == null)
                    return false;

                if (obj1.Vector.Length != obj2.Vector.Length)
                    return false;

                for (int i = 0; i < obj1.Vector.Length; i++)
                    if (obj1.Vector[i] != obj2.Vector[i])
                        return false;

                return true;
            }

            /// <summary>
            /// 比较是否两个对象是否属性一致
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="obj1">第一个对象</param>
            /// <param name="vector">第二个对象</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns></returns>
            public static bool IsPlayerEqual(KmeansCenterVector obj1, double[] vector)
            {
                if (object.ReferenceEquals(obj1.Vector, vector))
                    return true;
                if (obj1.Vector == null || vector == null)
                    return false;

                if (obj1.Vector.Length != vector.Length)
                    return false;

                for (int i = 0; i < obj1.Vector.Length; i++)
                    if (obj1.Vector[i] != vector[i])
                        return false;

                return true;
            }

            /// <summary>
            /// 创建中心点伪对象
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="list">数据点列表</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <param name="createAction">创建中心点伪对象的委托</param>
            /// <returns>中心点伪对象</returns>
            public static double[] CreatePseudoCenterObject<TKmeansObject>(IEnumerable<KmeansObjectWrapper<TKmeansObject>> list)
            {
                if (list == null)
                    throw new ArgumentNullException(nameof(list));

                double[] vector = null;
                double[] sum = null;
                int expectedFieldCount = 0;
                int count = 0;
                foreach (var item in list)
                {
                    if (vector == null)
                    {
                        vector = item.Vector;
                        expectedFieldCount = vector.Length;
                        sum = new double[expectedFieldCount];
                    }
                    else
                    {
                        vector = item.Vector;
                        if (vector.Length != expectedFieldCount)
                            throw new InvalidOperationException();
                    }
                    for (int i = 0; i < expectedFieldCount; i++)
                        sum[i] += vector[i];
                    count++;
                }
                if (count == 0)
                    return null;
                for (int i = 0; i < expectedFieldCount; i++)
                    sum[i] /= count;
                return sum;
            }

            /// <summary>
            /// 使用欧几里得算法计算两个数据点之间的距离
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="obj1">一个数据点</param>
            /// <param name="obj2">另一个数据点</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns>两个数据点之间的距离</returns>
            public static double CalculateDistence<TKmeansObject>(KmeansObjectWrapper<TKmeansObject> obj1, KmeansObjectWrapper<TKmeansObject> obj2)
            {
                if (object.ReferenceEquals(obj1, obj2))
                    return 0;

                double[] vector1;
                if (obj1.Vector == null)
                {
                    vector1 = obj2.Vector;
                    return Math.Sqrt(vector1.Select(d => d * d).Sum());
                }
                if (obj2.Vector == null)
                {
                    vector1 = obj1.Vector;
                    return Math.Sqrt(vector1.Select(d => d * d).Sum());
                }

                vector1 = obj1.Vector;
                double[] vector2 = obj2.Vector;

                if (vector1.Length != vector2.Length)
                    throw new InvalidOperationException();

                double dist = 0;
                for (int i = 0; i < vector1.Length; i++)
                    dist += Math.Pow(vector1[i] - vector2[i], 2);
                return Math.Sqrt(dist);
            }

            /// <summary>
            /// 使用欧几里得算法计算数据点和中心点之间的距离
            /// </summary>
            /// <typeparam name="TKmeansObject">数据对象类型</typeparam>
            /// <param name="obj1">一个数据点</param>
            /// <param name="center">中心点</param>
            /// <param name="vectorAction">用于从对象中提取指数的委托</param>
            /// <returns>两个数据点之间的距离</returns>
            public static double CalculateDistence<TKmeansObject>(KmeansObjectWrapper<TKmeansObject> obj1, KmeansCenterVector center)
            {
                if (object.ReferenceEquals(obj1, center.Vector))
                    return 0;

                double[] vector1;
                if (obj1.Vector == null)
                {
                    vector1 = center.Vector;
                    return Math.Sqrt(vector1.Select(d => d * d).Sum());
                }
                if (center.Vector == null)
                {
                    vector1 = obj1.Vector;
                    return Math.Sqrt(vector1.Select(d => d * d).Sum());
                }

                vector1 = obj1.Vector;
                double[] vector2 = center.Vector;

                if (vector1.Length != vector2.Length)
                    throw new InvalidOperationException();

                double dist = 0;
                for (int i = 0; i < vector1.Length; i++)
                    dist += Math.Pow(vector1[i] - vector2[i], 2);
                return Math.Sqrt(dist);
            }

            /// <summary>
            /// 从距离数组中找到最小距离的下标
            /// </summary>
            /// <param name="dists">距离数组</param>
            /// <returns>最小距离的下标</returns>
            public static int FindMinimumDistence(double[] dists)
            {
                double min = 0;
                int index = 0;
                for (int i = 0; i < dists.Length - 1; i++)
                {
                    double temp = dists[i];
                    if (i == 0)
                    {
                        min = temp;
                        index = 0;
                    }
                    temp = dists[i + 1];
                    if (min > temp)
                    {
                        min = temp;
                        index = i + 1;
                    }
                }
                return index;
            }
        }
    }

}
